/*
 * @Author: 生俊甫 1758142861@qq.com
 * @Date: 2024-10-26 18:47:20
 * @LastEditors: 生俊甫 1758142861@qq.com
 * @LastEditTime: 2024-10-28 16:54:06
 * @FilePath: /sjf/2024-project/2024_centos/test_to_c/408_str/2019.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <iostream>

/**
 * 2019年408真题的41题
 * 该题目主要使用的是
 * 1.寻找中间节点
 * 2.反转中间节点之后的节点
 * 3.讲这两个不同的链表合并
 * 例如 1，2，3，4，5，6，7，8，9
 *     中间节点为5
 *     然后分为了两个链表(1,2,3,4) (5,6,7,8,9)
 *     反转后面的链表为(1,2,3,4) (9,8,7,6,5)
 *     最后合并为(1,9,2,8,3,7,4,6,5)
 * 该题目为leetcode上题目
 * https://leetcode.cn/problems/reorder-list/
 */


struct ListNode {
    int val;
    struct ListNode *next;
 };

//寻找中间节点
struct ListNode* middle_node(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

//逆序后半链表
struct ListNode* reverse_list(struct ListNode* head)
{
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = n2->next;
    while(n2 != NULL)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3 != NULL)
            n3 = n3->next;
   }
   return n1;
}

//合并
void merge_list(struct ListNode* head1,struct ListNode* head2)
{
    struct ListNode* cur1;
    struct ListNode* cur2;
    while(head1 != NULL && head2 != NULL)
    {
        cur1 = head1->next;
        cur2 = head2->next;

        head1->next = head2;
        head1 = cur1;

        head2->next = head1;
        head2 = cur2;
    }
}
//合并两个链表
void reorderList(struct ListNode* head) {
    if(head == NULL)
        return;
    struct ListNode* mid = middle_node(head);
    struct ListNode* l1 = head;
    struct ListNode* l2 = mid->next;
    mid->next = NULL;
    l2 = reverse_list(l2);
    merge_list(l1,l2);
}


int main()
{
    return 0;
}